package 并查集.模板;

/*
    做完题一定写入表格
*/
public class ConnectFind {
    //p[a]=b a的父亲是b
    public int[] p;
    //*子树结点总个数
    public int[] s;
    //岛屿数量
    public int daoyu;

    //【准备】
    public ConnectFind(int n){
        p=new int[n]; s =new int[n]; daoyu=n;

        for (int i = 0; i < n; i++) {
            p[i]=i;
            s[i]=1;
        }
    }
    public int find_returnRot(int i){
        while(p[i]!=i){
            //压缩2个为一层
            p[i]=p[p[i]];
            i = p[i];
        }
        return i;
    }
    //[核心] 个数少的根接到个数多的根下 （不用长短！）
    public void connect(int a,int b){
        int aR = find_returnRot(a);
        int bR = find_returnRot(b);
        //根同时：1不用连2岛屿数不减
        if(aR==bR){
            return;
        }

        if(s[aR]< s[bR]){
            p[aR]=bR;
            //为什么不用最长深度比？ 1代码复杂 2(虽然以人视角看着整体好)只能照顾一个分支，找不过来的
            s[aR] += s[bR];
        }else{
            p[bR]=aR;
            s[bR] += s[aR];
        }
        daoyu--;
    }

    //【使用】判断是否相连
    public boolean judgeCon(int a, int b){
        return find_returnRot(a)==find_returnRot(b);
    }
}
